package com.c2b.algorithm.leetcode.base.sliding_window;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/"/>找到字符串中所有字母异位词(Find All Anagrams in a String)</a>
 * <p>给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。</p>
 * <p>异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: s = "cbaebabacd", p = "abc"
 *      输出: [0,6]
 *      解释:
 *          起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 *          起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *
 *  示例 2:
 *      输入: s = "abab", p = "ab"
 *      输出: [0,1,2]
 *      解释:
 *          起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 *          起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 *          起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *  <ul>
 *     <li>1 <= s.length, p.length <= 3 * 10^4</li>
 *     <li>s 和 p 仅包含小写字母</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/30 17:51
 */
public class LC0438FindAllAnagramsInString_M {
    static class Solution {

        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> retList = new ArrayList<>();
            int sLen = s.length();
            int pLen = p.length();
            if (sLen < pLen) {
                return retList;
            }
            // 记录滑动窗口内，各个字符的差异数量
            int[] differCountArr = new int[26];
            for (int i = 0; i < pLen; i++) {
                differCountArr[s.charAt(i) - 'a']++;
                differCountArr[p.charAt(i) - 'a']--;
            }
            // 记录滑动窗口内，差异字符的总数量
            int differ = 0;
            for (int i : differCountArr) {
                if (i != 0) {
                    ++differ;
                }
            }
            if (differ == 0) {
                retList.add(0);
            }
            for (int i = 0; i < sLen - pLen; i++) {
                // 当前字符所在的下标位置
                int currCharIndex = s.charAt(i) - 'a';
                // 处理窗口中的第一个元素：该元素将会被移出窗口
                // 1.如果当前字符的差异数量为1，移出窗口后数量将会变为 0 ==> 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同 ==> differ-1
                // 2.如果当前字符的差异数量为0，移出窗口后数量将会变为-1 ==> 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同 ==> differ+1
                // 3.如果当前字符的差异数量为其他值，差异数量只会增加或者减少，不影响differ
                if (differCountArr[currCharIndex] == 1) {
                    --differ;
                } else if (differCountArr[currCharIndex] == 0) {
                    ++differ;
                }
                // 移出窗口
                --differCountArr[currCharIndex];

                // 下一字符所在的下标位置
                int nextCharIndex = s.charAt(i + pLen) - 'a';
                // 处理窗口尾部的下一个元素：该元素将会进入窗口
                // 1.如果当前字符的差异数量为-1，进入窗口数量将会变为0 ==> 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同 ==> differ-1
                // 2.如果当前字符的差异数量为 0，进入窗口数量将会变为1 ==> 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同 ==> differ+1
                // 3.如果当前字符的差异数量为其他值，差异数量只会增加或者减少，不影响differ
                if (differCountArr[nextCharIndex] == -1) {
                    --differ;
                } else if (differCountArr[nextCharIndex] == 0) {
                    ++differ;
                }
                // 进入窗口
                ++differCountArr[nextCharIndex];

                // 如果字符恰好匹配，计入结果
                if (differ == 0) {
                    retList.add(i + 1);
                }
            }
            return retList;
        }


        public List<Integer> findAnagrams2(String s, String p) {
            List<Integer> retList = new ArrayList<>();
            int sLen = s.length();
            int pLen = p.length();
            if (sLen < pLen) {
                return retList;
            }
            int[] sCountArr = new int[26];
            int[] pCountArr = new int[26];
            for (int i = 0; i < pLen; i++) {
                sCountArr[s.charAt(i) - 'a']++;
                pCountArr[p.charAt(i) - 'a']++;
            }
            if (Arrays.equals(sCountArr, pCountArr)) {
                retList.add(0);
            }
            for (int i = 0; i < sLen - pLen; i++) {
                sCountArr[s.charAt(i) - 'a']--;
                sCountArr[s.charAt(i + pLen) - 'a']++;
                if (Arrays.equals(sCountArr, pCountArr)) {
                    retList.add(i + 1);
                }
            }
            return retList;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (Integer anagram : solution.findAnagrams("aaaaa", "dddd")) {
            System.out.println(anagram);
        }
    }
}
